The present invention relates to a method of allocating to users shared resources in a telecommunications network. It is particularly directed at allocating resources such as transmission bandwidth in a network handling a mixture of traffic types such as voice and data by means of a resource allocation method which takes account of a user""s stated willingness to pay for use of network resources.
In any communications network where there is competition between users for resources, whether those resources are bandwidth, switching capacity, buffer occupancy or other resources, there must be an agreed strategy for dividing those resources when the combined demand from the users exceeds the network resource capacity. Historically, different strategies have been developed for different network and traffic types, and their behaviour under varying load conditions is generally understood. However neither of the two main strategies, call-blocking for circuit-switched, constant bit rate, real-time applications; bit rate reduction and packet/cell loss for packet-switched, variable bit rate, non-real-time applications, are particularly suitable for use in networks which carry mixtures of both of these traffic types together with other types, such as real-time video, which may require variable bit rates for real-time applications.
Another shortcoming of these approaches is their failure to recognise that different users place different, subjective values on their communications and that the value an individual user places on his communications may vary. The result of this is that when the network is congested, a user who wishes to engage in what he perceives as high value communication, for which he would be prepared to pay a significant premium if doing so guaranteed him access and/or a better quality of service, may be blocked (circuit-switched) or have his communication significantly delayed, or reduced in quality (packet switched) by other users whose communication is of lower value.
The issues of charging, rate control and routing for a communications network carrying elastic (data) traffic, such as an ATM network, are discussed in a paper authored by Frank Kelly entitled xe2x80x9cCharging and Rate Control for Elastic Trafficxe2x80x9d published in European Transactions on Telecommunications, volume 8(1997), pages 33-37. This paper introduces the concept of allocating a resource in a proportionally fair manner. If all users are willing to pay the same price per unit bandwidth then the proportionally fair distribution of a network resource is given by the set of traffic flows xs that satisfy the inequality:                                           ∑                          s              ∈              S                                ⁢                                                    x                s                *                            -                              x                s                                                    x              s                                      ≤        0                            (        1        )            
for all alternative feasible sets of flows xs* where S is the set of source-sinks s. A source-sink comprises a connection across a network between an ingress node and a destination node. In other words, a source-sink comprises a route across the network. If users offer different willingness to pay values, then each term in the sum in equation 1 is scaled by that value, giving:                                           ∑                          s              ∈              S                                ⁢                                                    m                s                            ⁡                              (                                                      x                    s                    *                                    -                                      x                    s                                                  )                                                    x              s                                      ≤        0                            (        2        )            
where ms is the stated willingness to pay associated with source-sink s.
This is equivalent, if the users"" perceived benefit from the bandwidth they are allocated is proportional to the log of the bandwidth, to finding the set of flows xs that maximise the equation                               ∑                      s            ∈            S                          ⁢                              m            s                    ⁢          ln          ⁢                      xe2x80x83                    ⁢                      x            s                                              (        3        )            
subject to the constraint that none of the network resources should be over-utilised.
A consequence of selecting the proportionally fair traffic distribution is that a network resource will only be under-utilised if increasing its utilisation (by increasing one or more of the flows through the resource) has a net negative effect on the total user utility, as defined in equation 3. If a given resource is used by a flow which only uses that resource, then the proportionally fair traffic distribution will necessarily fully utilise that resourcexe2x80x94since if the resource were not fully utilised, the flow through it which only used that resource could be increased without any xe2x80x98knock-onxe2x80x99 effect on other users"" flows. This would result in an increased total user utility, contradicting the claim that the previous set of flows had resulted in maximum user utility.
However, in an arbitrary network, there will be several alternative routes between any given pair of nodes. In general, proportional fairness criteria alone are unable therefore to determine which routes or combinations of routes will result in maximum user utilityxe2x80x94the utility function described in equation 3 may be maximised by several distinct sets of flows which result when different routing options are selected. Consequently, some other criteria are necessary to determine which of the equivalent sets of flows should be implemented.
A crude method of subjecting users"" communications in a telecommunications network to some sort of value consideration is to set different charging rates (tariffs) for different types of calls and for predefined periods. More often, this results in increased network operator revenues but does exert some influence on users"" call behaviour particularly with respect to expected periods of high demand closely matching or exceeding network capacity. However, this method is merely an extension of the known strategies of call blocking and bit rate reduction and does not result in a proportionally fair allocation of network resources.
The bandwidth and Quality of Service (QoS) requirements of different calls can impose greatly differing loads on the network. Usage-sensitive charging can be employed to ensure that call charges properly reflect the loading on the network. Charging more heavily at times of peak load provides an incentive for customers to prioritise their traffic appropriately. An efficient charging method should enable customers to predict their costs and network operators to predict their revenues. However, in a multi-service environment charging methods become complex in order to ensure that charges suitably reflect the loads that calls impose on the network by virtue of their characteristics and QoS requirements. The development of such methods raises fundamental questions about how to characterise network load, to what extent should customers be involved in declaring their traffic load and priorities, and how significant are usage-related costs relative to other fixed network costs.
One issue that must be addressed is how price should vary dynamically or responsively to follow changes in a network""s state. Such a pricing mechanism may convince users not to transmit when the network is becoming congested. Dynamic state-dependant pricing will, however, appear to users as prices that fluctuate randomly, which is not generally a desirable property. It is pointless in applications where humans rather than computers directly determine when transmissions are made. It is hard to imagine a person watching the tariff for making a long-distance call fluctuate widely on a meter, waiting for the perfect moment to make such a call. However, there are applications where dynamic pricing makes sense. For example, a user wandering the World Wide Web (WWW) might instruct his browser to suspend operation, or to retrieve text not images, or to simply decrease the data rate, when tariffs are high.
Present charging methods such as peak-rate tariffs are incapable of ensuring a proportionally fair allocation of network resources between users in any network where users place different values on their communications.
The invention seeks to provide a method of allocating shared resources in a telecommunications network which obviates some of the problems associated with known charging methods.
The invention also seeks to provide a method of allocating resources in a telecommunications network in accordance with users"" stated willingnesses to pay for said resources.
The invention also seeks to provide a telecommunications network in which users are allocated available resources in accordance with their willingnesses to pay for use of network resources.
The present invention provides a resource allocation method which is based on the concept of proportional fairness. In this method, users express their willingnesses to pay for network resources. A controller determines how the users"" willingnesses to pay are to be divided between the resources in order to determine the relative demands for the resources. Each resource is then divided between those users using it in proportion to how much they are willing to pay for the use of their share of it. The allocation takes into account the relative demands on all the resources in the network. A user may increase his share of the network resources allocated to him by increasing the value of his willingness to pay. The method may be applied either by a central controller (network manager), or it may be delegated to controllers (network element managers/customer premises equipment managers) distributed across the network.
In a dynamic system where the demand for resources is varying rapidly, provided adequate quality of service (e.g. cell loss ratio) can be maintained, then it is better to allow distributed controllers to react to local changes quickly than wait for whole network changes to reach a central controller. In other words, in a centralised control system the resources will not be fully utilised at the times in between when demand change over decisions are made and users"" reactions to these are made. In a distributed control system, each controller can use the resources more efficiently locally immediate to demand changes and this leads to a more optimum use of the resources.
The present invention therefore also provides a distributed resource allocation method. The distributed resource allocation method is also based on the concept of proportional fairness. In this method, users express their willingnesses to pay to the local distributed controller which is associated with those users. The bandwidth allocated to each user is determined by the local controller with which they are associated and the allocation takes into account the relative demands on all the resources in the network and the time taken for those demands to reach the distributed local controllers. The distributed controllers each use only locally available information at their respective nodes, but take into account the delays between nodes. The locally available resource (i.e. bandwidth) is divided in proportion to the willingnesses to pay expressed by the various users entering their particular node. On a ring (and in other networks where the only place that traffic streams are multiplexed is at the periphery) this guarantees that no data will be lost (due to cell/packet collision) once it has been launched.
The preferred features of the invention which are more fully defined in the appended claims may be combined as appropriate and as would be apparent to a skilled person.